package Leetcode.动态规划;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/3/27 16:39
 * @Description:
 * 三角形最小路径和
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * ------------
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *--------------
 *
 *
 * 示例 1：
 *
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * 示例 2：
 *
 * 输入：triangle = [[-10]]
 * 输出：-10
 *
 *
 * 提示：
 *
 * 1 <= triangle.length <= 200
 * triangle[0].length == 1
 * triangle[i].length == triangle[i - 1].length + 1
 * -104 <= triangle[i][j] <= 104
 */

public class minimumTotal {
    /**
     *按照题目给的思路逻辑，每次遍历判断求和
     * 三角形第i层就会有i个元素   i层第j个元素能到达i+1层第j或j+1元素
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        // 获取三角形的行数，也就是矩阵的列数
        int n = triangle.size();
        // 创建一个动态规划数组dp，用来保存从顶部到底部的最短路径和
        int[][] dp = new int[n][n];
        // 初始化起点，即三角形的底部左角元素
        dp[0][0] = triangle.get(0).get(0);
        // 从第二行开始填充dp数组
        for (int i = 1; i < n; ++i) {
            // 每一行的第一个元素是上一行的相邻两个元素之和加上当前行的第一个元素
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            // 中间的元素是上一行的左右相邻元素之和加上当前行的该元素
            for (int j = 1; j < i; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            // 每一行的最后一个元素是上一行的相邻两个元素之和加上当前行的最后一个元素
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        // 初始化最小总和为三角形的顶部元素
        int minTotal = dp[n-1][0];
        // 从顶部到底部路径的和
        for (int i = 1; i < n; ++i) {
            // 更新最小总和，取到达每一个底部元素的最小路径和
            minTotal = Math.min(minTotal, dp[n - 1][i]);
        }
        // 返回所有可能的路径中最小的路径和
        return minTotal;
    }


}
